package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//18. 四数之和

//给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
//
//注意：
//
//答案中不可以包含重复的四元组。
//
//示例：
//
//给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
//
//满足要求的四元组集合为：
//[
//  [-1,  0, 0, 1],
//  [-2, -1, 1, 2],
//  [-2,  0, 0, 2]
//]

public class Solution018 {
	public List<List<Integer>> fourSum(int[] nums, int target) {
		List<List<Integer>> res = new ArrayList<>();
		
		if (nums == null || nums.length < 4) {
			return res;
		}
		
		Arrays.sort(nums);
		
		for (int i=0; i<nums.length-3; i++) {
			
			if (i > 0 && nums[i] == nums[i-1]) {
				continue;
			}
			
			for (int j=i+1; j<nums.length-2; j++) {
				
				if (j > i+1 && nums[j] == nums[j-1]) {
					continue;
				}
				
				int left = j+1;
				int right = nums.length-1;
				
				while (left < right) {
					
					int sum = nums[i] + nums[j] + nums[left] + nums[right];
					
					if (sum == target) {
						
						List<Integer> list = new ArrayList<>();
						list.add(nums[i]);
						list.add(nums[j]);
						list.add(nums[left]);
						list.add(nums[right]);
						
						res.add(list);
						
						while (left < right && nums[left] == nums[left+1]) {
							left++;
						}
						while (left < right && nums[right] == nums[right-1]) {
							right--;
						}
						left++;
						right--;
						
						
					} else if(sum > target) {
						right--;
					} else {
						left++;
					}
					
					
				}
				
			}
			
		}
		
		return res;
    }
}
